package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/8/18.<br><br>
 *
 * 中等：有序数组中的单一元素
 */
public class Topic540 {

    public static void main(String[] args) {
        Topic540 instance = new Topic540();

        int[] array = new int[] {1,1,2,3,3,4,4,8,8};
        System.out.println(instance.singleNonDuplicate(array));

        array = new int[] {3,3,7,7,10,11,11};
        System.out.println(instance.singleNonDuplicate(array));

        array = new int[] {1};
        System.out.println(instance.singleNonDuplicate(array));
    }

    public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mild = (left + right) / 2;
            if((mild & 1) != 0) {
                mild--;
            }

            if(nums[mild] == nums[mild + 1]) {
                left = mild + 2;
            }
            else {
                right = mild;
            }
        }

        return nums[left];
    }

    public int singleNonDuplicate3(int[] nums) {
        if(nums.length == 1) {
            return nums[0];
        }

        return helper(nums, 0, nums.length - 1);
    }

    private int helper(int[] nums, int left, int right) {
        if(left > right) {
            return -1;
        }

        int mild = (left + right) / 2;
        if(mild == 0 && nums[mild] != nums[mild + 1]) {
            return nums[mild];
        }

        if(mild == nums.length - 1 && nums[mild] != nums[mild - 1]) {
            return nums[mild];
        }

        if(mild > 0 && nums[mild] != nums[mild - 1] && mild < nums.length - 1 && nums[mild] != nums[mild + 1]) {
            return nums[mild];
        }

        int resultL = helper(nums, left, mild - 1);
        int resultR = helper(nums, mild + 1, right);

        return resultL != -1 ? resultL : resultR;
    }

    public int singleNonDuplicate2(int[] nums) {
        int result = 0;

        for(int value : nums) {
            result ^= value;
        }

        return result;
    }
}
